<?php
require 'Map.php';

class BinarySearchTreeMap implements Map
{
    public $root;
    public $size;

    public function __construct()
    {
        $this->root = null;
        $this->size = 0;
    }

    /**
     * 获取映射(Map)中某个key对应的value
     * @param $key
     * @return |null
     */
    public function get($key)
    {
        $node = $this->recursionGet($key, $this->root);
        return $node == null ? null : $node->value;
    }

    /**
     * 递归获取 key 对应的节点
     * @param $key
     * @param $root
     * @return |null
     */
    private function recursionGet($key, $root)
    {
        if ($root == null) {
            return null;
        } elseif ($key == $root->key) {
            return $root;
        } elseif ($key < $root->key) {
            return $this->recursionGet($key, $root->left);
        } else {
            return $this->recursionGet($key, $root->right);
        }
    }

    /**
     * 添加 key-value 数据
     * @param $key
     * @param $value
     */
    public function add($key, $value): void
    {
        $this->root = $this->recursionAdd($key, $value, $this->root);
    }

    /**
     * 递归添加数据
     * @param $key
     * @param $value
     * @param $root
     */
    private function recursionAdd($key, $value, $root)
    {
        if ($root == null) {
            $root = new Node($key, $value);
            $this->size++;
        } elseif ($key == $root->key) {
            $root->value = $value;
        } elseif ($key < $root->key) {
            $root->left = $this->recursionAdd($key, $value, $root->left);
        } else {
            $root->right = $this->recursionAdd($key, $value, $root->right);
        }
        return $root;
    }

    /**
     * 查看map是否包含某个key
     * @param $key
     * @return bool
     */
    public function contains($key): bool
    {
        $node = $this->recursionGet($key, $this->root);
        return $node != null;
    }


    /**
     * 递归查看map是否存在某个 key
     * @param $key
     * @param $root
     * @return bool
     */
    private function recursionContains($key, $root)
    {
        if ($root == null) {
            return false;
        } elseif ($key == $root->key) {
            return true;
        } elseif ($key < $root->key) {
            return $this->recursionContains($key, $root->left);
        } else {
            return $this->recursionContains($key, $root->right);
        }
    }

    /**
     * 修改 key 对应的 value
     * @param $key
     * @param $value
     */
    function set($key, $value)
    {
        $node = $this->recursionGet($key, $this->root);
        if ($node == null) {
            echo "不存在该节点";
            exit;
        }

        $node->value = $value;
    }

    public function traverseMinHeap($minHeap, $k)
    {

        $this->recursionTraverse($this->root, $minHeap, $k);
    }

    private function recursionTraverse($root, $minHeap, $k)
    {

        if ($root != null) {
            $this->recursionTraverse($root->left, $minHeap, $k);
            if ($minHeap->getSize() < $k) {
                $minHeap->add(['key' => $root->key, 'value' => $root->value]);
            } else {
                $min = $minHeap->findMin();
                if ($root->value > $min['value']) {
                    $minHeap->replaceMin(['key' => $root->key, 'value' => $root->value]);
                }
            }

            $this->recursionTraverse($root->right, $minHeap, $k);
        }

    }

    /**
     * 删除二分搜索树元素
     * @param $e
     */
    public function remove($k)
    {
        $value = $this->get($k);
        $this->root = $this->recursionRemove($this->root, $k);
        return $value;
    }

    /**
     * 递归删除二分搜索树元素
     * @param $root
     * @param $e
     */
    private function recursionRemove($root, $k)
    {
        if ($root != null) {
            if ($k == $root->key) {
                $root = $this->joinRemoveNode($root);
            } elseif ($k < $root->key) {
                $root->left = $this->recursionRemove($root->left, $k);
            } else {
                $root->right = $this->recursionRemove($root->right, $k);
            }
        }
        return $root;
    }

    /**
     * 拼接删除节点 返回新节点
     */
    private function joinRemoveNode($root)
    {

        if ($root->left != null && $root->right == null) {
            $root = $root->left;
        } elseif ($root->left == null && $root->right != null) {
            $root = $root->right;
        } else {
            $leftMax = $this->getMaxNode($root->left);
            $leftMax->right = $root->right;
            $root = $root->left;
        }
        return $root;
    }

    /**
     * 获取某颗树最大元素节点
     * @param $root
     * @return mixed
     */
    private function getMaxNode($root)
    {
        for ($node = $root; $node != null; $node = $node->right) {
            if ($node->right != null) {
                $root = $node->right;
            } else {
                $root = $node;
            }
        }
        return $root;
    }

    /**
     * 获取最小元素
     * @return mixed
     */
    public function getMin()
    {
        return $this->getMinNode($this->root)->e;
    }

    /**
     * 获取某颗树最小元素节点
     * @param $root
     * @return mixed
     */
    private function getMinNode($root)
    {
        for ($node = $root; $node != null; $node = $node->left) {
            if ($node->left != null) {
                $root = $node->left;
            } else {
                $root = $node;
            }
        }
        return $root;
    }

    /**
     * 获取映射 Map 中 key-value 数量
     * @return int
     */
    public function getSize(): int
    {
        return $this->size;
    }
}

class Node
{
    public $key;
    public $value;
    public $left = null;
    public $right = null;

    public function __construct($key, $value)
    {
        $this->key = $key;
        $this->value = $value;
    }
}